leetcode 第一题 Two Sum

这是 leetcode 上算法的第一题，官方定位为简单题目，事实也是如此。题目地址

题目：给定一个整数数组，返回两个数字的返回索引，这样它们就可以添加到特定的目标。假设每个输入都只有一个结果，不会两次使用相同的元素。例如：

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 最简单的双重循环
var twoSum = function(nums, target) {
   var d ={};
    var result = [];
    for (var i = 0; i < nums.length; i++) {
        for (var j = 0; j < nums.length; j++) {
          if (nums[i] + nums[j] === target && i !== j) {
             (i < j) ? result.push(i, j) : result.push(j, i);
             return result;
          }
        }
    }
    return result;
};

基本所有人都会，但是该方法算法复杂度为O(n2)，运行时间过长(246ms)

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var twoSum = function(nums, target) {
    var d ={};
    var result = [];
    for (var i = 0; i < nums.length; i++) {
        var a = target - nums[i] +'';
        var t = {};
        d[a] = i;
    }
    for (var b = 0; b < nums.length; b++) {
        var c = nums[b]+'';
        if(d[c] !== undefined){
          var x = d[c], y = nums.indexOf(nums[b]);
          if (x !== y){
            (y < x) ? result.push(y, x) : result.push(x, y);
            return result;   
          }
        }
    }
    return result;
};

这种解法是用两个单独的循环，所以运行时间大大减少(116ms)。

大概思路是先做一遍遍历,将数据以’目标值减去数组中的某个值 : 该值的索引’这样类似map的方式存储在对象d中，然后再做一次遍历根据是否是新对象的属性来判断有没有解。 这个解法是我对这道题目的思考过程，中间有很多多余的操作。

解法三

1
2
3
4
5
6
7
8
9
10
11
12
13
var twoSum = function(nums, target) {
var ans = [];
var exist = {};
for (var i = 0; i < nums.length; i++){
    if (typeof(exist[target-nums[i]]) !== 'undefined'){
        ans.push(exist[target-nums[i]]);
        ans.push(i);
    }
    exist[nums[i]] = i;
}
return ans;
};

leetcode 上大佬的解法，运行时间（92ms），直接在一个循环中解决问题。

大致思路，就是遍历数组，在exis对象中存入’值’：’索引’的属性，使用typeof 判断是否有符合条件的属性，有的话存入ans,最后返回ans。

对于这个算法我本来想在ans.push(i)后加个 return ans，想这样不用把算法走完或许会再少点时间，但是时间反而多了一点。然后我又尝试用break，好像是减少了几ms，但是leetcode运行同样的算法时间都有变化，这个就算在误差内了。

这道题目虽然不是很难，但是加深了我对javascript基础的认知，也感受到了用javascript写算法与java这种面向对象语言的区别。